{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Score of an Array After Marking All Elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sorting #simulation #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #排序 #模拟 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #标记所有元素后数组的分数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组&nbsp;<code>nums</code>&nbsp;，它包含若干正整数。</p>\n",
    "\n",
    "<p>一开始分数&nbsp;<code>score = 0</code>&nbsp;，请你按照下面算法求出最后分数：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>从数组中选择最小且没有被标记的整数。如果有相等元素，选择下标最小的一个。</li>\n",
    "\t<li>将选中的整数加到&nbsp;<code>score</code>&nbsp;中。</li>\n",
    "\t<li>标记 <strong>被选中元素</strong>，如果有相邻元素，则同时标记&nbsp;<strong>与它相邻的两个元素</strong>&nbsp;。</li>\n",
    "\t<li>重复此过程直到数组中所有元素都被标记。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回执行上述算法后最后的分数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [2,1,3,4,5,2]\n",
    "<b>输出：</b>7\n",
    "<b>解释：</b>我们按照如下步骤标记元素：\n",
    "- 1 是最小未标记元素，所以标记它和相邻两个元素：[<em><strong>2</strong></em>,<em><strong>1</strong></em>,<em><strong>3</strong></em>,4,5,2] 。\n",
    "- 2 是最小未标记元素，所以标记它和左边相邻元素：[<em><strong>2</strong></em>,<em><strong>1</strong></em>,<em><strong>3</strong></em>,4,<em><strong>5</strong></em>,<em><strong>2</strong></em>] 。\n",
    "- 4 是仅剩唯一未标记的元素，所以我们标记它：[<em><strong>2</strong></em>,<em><strong>1</strong></em>,<em><strong>3</strong></em>,<em><strong>4</strong></em>,<em><strong>5</strong></em>,<em><strong>2</strong></em>] 。\n",
    "总得分为 1 + 2 + 4 = 7 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [2,3,5,1,3,2]\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>我们按照如下步骤标记元素：\n",
    "- 1 是最小未标记元素，所以标记它和相邻两个元素：[2,3,<em><strong>5</strong></em>,<em><strong>1</strong></em>,<em><strong>3</strong></em>,2] 。\n",
    "- 2 是最小未标记元素，由于有两个 2 ，我们选择最左边的一个 2 ，也就是下标为 0 处的 2 ，以及它右边相邻的元素：[<em><strong>2</strong></em>,<em><strong>3</strong></em>,<em><strong>5</strong></em>,<em><strong>1</strong></em>,<em><strong>3</strong></em>,2] 。\n",
    "- 2 是仅剩唯一未标记的元素，所以我们标记它：[<em><strong>2</strong></em>,<em><strong>3</strong></em>,<em><strong>5</strong></em>,<em><strong>1</strong></em>,<em><strong>3</strong></em>,<em><strong>2</strong></em>] 。\n",
    "总得分为 1 + 2 + 2 = 5 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-score-of-an-array-after-marking-all-elements](https://leetcode.cn/problems/find-score-of-an-array-after-marking-all-elements/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-score-of-an-array-after-marking-all-elements](https://leetcode.cn/problems/find-score-of-an-array-after-marking-all-elements/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,3,4,5,2]', '[2,3,5,1,3,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/u/l00/\n",
    "\n",
    "\"\"\"\n",
    "贪心 + 反悔\n",
    "\n",
    "观察局部 xxx213xxx 可发现，无论前后 xxx 换成什么数字，由于 213 包裹了 1 ，所以 1 怎么都会被选中，2和3怎么都不会被选中，甚至改成 xxx978xxx 也是一样的结论，可以理解为由于中间比两边小，无论如何都是选中中间的数字而两边数字只能作废，那么局部看这个结构是固定的，不随其他外部数字所改变，那么我们能否从左到右逐个分析筛选出全部满足这种条件的局部而得到整体的答案？\n",
    "\n",
    "我们可以稍微扩展一下这个范围，或者说限制范围，我们就从左到右分析，那么已知之前最优结构的答案是 ans，那么我们当前可以分析当一个数子是否被选中，如果选中了，当前数字如果比前一个数字大，明显就是 213 结构的 3 了，如果我们比之前的数字小，那么可能是 213 结构的 1 ，如果是 1 ，需要反悔之前选中的 2 ，而每次这种反悔重选也需要给出一个反悔当前选择的值，所以可以用 backtrack[i -1] 代表如果选中当前下标需要的反悔的添加，而反悔当前选择的 backtrack[i] 则等于把当前值和反悔都减回去，形成循环；\n",
    "\n",
    "再分析可以发现不需要使用数组，因为反悔仅用到 backtrack[i - 1] ，直接用变量代替即可\n",
    " \"\"\"\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        backtrack = -nums[0]\n",
    "        ans = nums[0]\n",
    "        for idx,num in enumerate(nums[1:], 1):\n",
    "            if backtrack != 0 and nums[idx - 1] <= num:\n",
    "                backtrack = 0\n",
    "                continue\n",
    "            if backtrack != 0 and nums[idx - 1] > num:\n",
    "                ans += nums[idx] + backtrack\n",
    "                backtrack = - nums[idx] - backtrack\n",
    "            else:\n",
    "                ans += num\n",
    "                backtrack = -num\n",
    "        return ans\n",
    "\n",
    "# 直接模拟\n",
    "# class Solution:\n",
    "#     def findScore(self, nums: List[int]) -> int:\n",
    "#         n = len(nums)\n",
    "#         v = [False] * n\n",
    "#         li = sorted((val,i) for i,val in enumerate(nums))\n",
    "#         ans = 0\n",
    "#         for val,i in li:\n",
    "#             if v[i]: continue\n",
    "#             ans += val\n",
    "#             v[i] = True\n",
    "#             if i > 0: v[i - 1] = True\n",
    "#             if i < n - 1: v[i + 1] = True\n",
    "#         return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n,res,i=len(nums),0,0\n",
    "        while i<n:\n",
    "            j=i\n",
    "            while j+1<n and nums[j]>nums[j+1]:\n",
    "                j +=1\n",
    "            for k in range(j,i-1,-2):\n",
    "                res +=nums[k]\n",
    "            i=j+2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        res,i,n=0,0,len(nums)\n",
    "        while i<n:\n",
    "            j=i\n",
    "            while j+1<n and nums[j]>nums[j+1]:\n",
    "                j +=1\n",
    "            for k in range(j,i-1,-2):\n",
    "                res +=nums[k]\n",
    "\n",
    "            i=j+2\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        i, n = 0, len(nums)\n",
    "        while i < n:\n",
    "            i0 = i\n",
    "            while i + 1 < n and nums[i] > nums[i + 1]:\n",
    "                i += 1\n",
    "            j = i\n",
    "            while j >= i0:\n",
    "                ans += nums[j]\n",
    "                j -= 2\n",
    "            i += 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        i, n = 0, len(nums)\n",
    "        while i < n:\n",
    "            i0 = i\n",
    "            while i + 1 < n and nums[i] > nums[i + 1]:  # 找到下坡的坡底\n",
    "                i += 1\n",
    "            for j in range(i, i0 - 1, -2):  # 从坡底 i 到坡顶 i0，每隔一个累加\n",
    "                ans += nums[j]\n",
    "            i += 2  # i 选了 i+1 不能选\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        # n = len(nums)\n",
    "        # ans = 0\n",
    "        # used = [False] * (n + 2)\n",
    "        # for i, x in sorted(enumerate(nums, 1), key=lambda p : p[1]):\n",
    "        #     if not used[i]:\n",
    "        #         used[i-1] = used[i+1] = True\n",
    "        #         ans += x\n",
    "        # return ans\n",
    "        ans = 0\n",
    "        i, n = 0, len(nums)\n",
    "        while i < n:\n",
    "            i0 = i\n",
    "            while i + 1 < n and nums[i] > nums[i + 1]:\n",
    "                i += 1\n",
    "            for j in range(i, i0-1, -2):\n",
    "                ans += nums[j]\n",
    "            i += 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/u/l00/\n",
    "\n",
    "\"\"\" \n",
    "局部分析 xxx213xxx 可以看到 213 中的 1 一定会被选，2和3一定作废，且外部xxx是什么都无法改变这个规律，所以可以不断扩展这个结构使之得到答案；\n",
    "\n",
    "如果前一步的最优解是ans，那么情况有3种，特别的是如果前一个数字是选中的情况，当前数字比之前小，那么可能是 213 中 1 的情况。如果比之前大那么可能是 213 中 3 的情况。那么如果想选当前的选择就必须反悔之前的选择，就需要维护一个 backtrack[i - 1] ，表示反悔前一个选择需要回加多少数值，而当前 backtrack[i] 就等于是把当前选中的数值和之前反悔又还原回去；\n",
    "\n",
    "最后再分析可以发现 backtrack 只用到 [i - 1] 其他没有意义，故一个变量代替即可；\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        backtrack = -nums[0]\n",
    "        ans = nums[0]\n",
    "        # 前面被选中 backtrack 就不会为 0 ，因为为 0 等于与之前相等，但如果相等肯定是下标小的选中，而下标大的会被抛弃故还是 0 ；\n",
    "        # 情况一：前面一个没有选中，那么当前就是 213 后面的新开始，从新选择；\n",
    "        # 情况二：前面一个选中，当前的更小，那么当前就是 213 的 1 选 1 并反悔之前选的 2；\n",
    "        # 情况三：前面一个选中，当前的更大，那么当前就是 213 的 3 这是作废选项反悔清零；\n",
    "        for idx,num in enumerate(nums[1:], 1):\n",
    "            if backtrack == 0:\n",
    "                ans += num\n",
    "                backtrack = -num\n",
    "            else:\n",
    "                if nums[idx - 1] > num:\n",
    "                    ans += nums[idx] + backtrack\n",
    "                    backtrack = - nums[idx] - backtrack\n",
    "                else: backtrack = 0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        s=set()   \n",
    "        ans=0\n",
    "        for i,x in sorted(enumerate(nums),key=lambda z:(z[1],z[0])):\n",
    "            if i not in s:\n",
    "                s.add(i)\n",
    "                s.add(i-1)\n",
    "                s.add(i+1)\n",
    "                ans+=x\n",
    "        return ans\n",
    "        '''\n",
    "        '''\n",
    "        #也可以用数组的方式来模拟哈希表\n",
    "        ans=0\n",
    "        vis=[False]*(len(nums)+2)\n",
    "        for i,x in sorted(enumerate(nums,1),key=lambda z:z[1]):\n",
    "            if not vis[i]:\n",
    "                ans+=x\n",
    "                vis[i+1]=vis[i-1]=True  #这是因为把相邻的标记上了，自己肯定不会被再次选中了，本来也就只用标记相邻的\n",
    "        return ans\n",
    "        '''\n",
    "        #接下来是O(n)的做法,把数组看成一段一段的山脉\n",
    "        ans=0\n",
    "        i=0 #记录第一段山脉的其实下标\n",
    "        while i<len(nums):\n",
    "            j=i\n",
    "            while j+1<len(nums) and nums[j+1]<nums[j]:j+=1\n",
    "            #找到山脚了，倒叙遍历回去\n",
    "            for k in range(j,i-1,-2):\n",
    "                ans+=nums[k]\n",
    "            i=j+2\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        i, n = 0, len(nums)\n",
    "        while i < n:\n",
    "            i0 = i\n",
    "            while i + 1 < n and nums[i] > nums[i + 1]:\n",
    "                i += 1\n",
    "            ans += nums[i]\n",
    "            j = i - 2\n",
    "            while j >= i0:\n",
    "                ans += nums[j]\n",
    "                j -= 2\n",
    "            i += 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# dp\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1: return nums[0]\n",
    "        dps = [0] * n\n",
    "        dps[0] = -nums[0]\n",
    "        ans = nums[0]\n",
    "        idx = 1\n",
    "        for idx in range(1,n):\n",
    "            if dps[idx - 1] != 0 and nums[idx - 1] <= nums[idx]: continue\n",
    "            if dps[idx - 1] != 0 and nums[idx - 1] > nums[idx]:\n",
    "                ans += nums[idx] + dps[idx - 1]\n",
    "                # dps[idx] = nums[idx] - nums[idx - 1] +\n",
    "                dps[idx] = - nums[idx] - dps[idx - 1]\n",
    "            else:\n",
    "                ans += nums[idx]\n",
    "                dps[idx] = -nums[idx]\n",
    "        #     print(idx,nums[idx],ans)\n",
    "        # print(dps)\n",
    "        return ans\n",
    "\n",
    "# 直接模拟\n",
    "# class Solution:\n",
    "#     def findScore(self, nums: List[int]) -> int:\n",
    "#         n = len(nums)\n",
    "#         v = [False] * n\n",
    "#         li = sorted((val,i) for i,val in enumerate(nums))\n",
    "#         ans = 0\n",
    "#         for val,i in li:\n",
    "#             if v[i]: continue\n",
    "#             ans += val\n",
    "#             v[i] = True\n",
    "#             if i > 0: v[i - 1] = True\n",
    "#             if i < n - 1: v[i + 1] = True\n",
    "#         return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        nums = [inf] + nums + [inf]\n",
    "        l, r, lenn, ans = 1, 2, len(nums), 0\n",
    "        while r < lenn:            \n",
    "            if nums[r] >= nums[l]:\n",
    "                while r < lenn and nums[r] >= nums[r - 1]: r += 1\n",
    "                ans += sum(nums[l : r - 1 : 2])\n",
    "                l = r - (r - l & 1)\n",
    "            else:      \n",
    "                while r < lenn and nums[r] < nums[r - 1]: r += 1\n",
    "                ans += sum(nums[l if r - l & 1 else l + 1: r : 2])\n",
    "                l = r + 1\n",
    "            r = l + 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        nums = [inf] + nums + [inf]\n",
    "        l, r, lenn, ans = 1, 2, len(nums), 0\n",
    "        while r < lenn:            \n",
    "            if nums[r] >= nums[l]:\n",
    "                while r < lenn and nums[r] >= nums[r - 1]: r += 1\n",
    "                ans += sum(nums[l : r - 1 : 2])\n",
    "                l = r - (r - l & 1)\n",
    "            else:      \n",
    "                while r < lenn and nums[r] < nums[r - 1]: r += 1\n",
    "                ans += sum(nums[l if r - l & 1 else l + 1: r : 2])\n",
    "                l = r + 1\n",
    "            r = l + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# dp\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1: return nums[0]\n",
    "        v = [False] * n\n",
    "        v[0] = True\n",
    "        dps = [0] * n\n",
    "        dps[0] = -nums[0]\n",
    "        ans = nums[0]\n",
    "        idx = 1\n",
    "        for idx in range(1,n):\n",
    "            if dps[idx - 1] != 0 and nums[idx - 1] <= nums[idx]: continue\n",
    "            if dps[idx - 1] != 0 and nums[idx - 1] > nums[idx]:\n",
    "                ans += nums[idx] + dps[idx - 1]\n",
    "                # dps[idx] = nums[idx] - nums[idx - 1] +\n",
    "                dps[idx] = - nums[idx] - dps[idx - 1]\n",
    "            elif dps[idx - 1] == 0:\n",
    "                ans += nums[idx]\n",
    "                dps[idx] = -nums[idx]\n",
    "        #     print(idx,nums[idx],ans)\n",
    "        # print(dps)\n",
    "        return ans\n",
    "\n",
    "# 直接模拟\n",
    "# class Solution:\n",
    "#     def findScore(self, nums: List[int]) -> int:\n",
    "#         n = len(nums)\n",
    "#         v = [False] * n\n",
    "#         li = sorted((val,i) for i,val in enumerate(nums))\n",
    "#         ans = 0\n",
    "#         for val,i in li:\n",
    "#             if v[i]: continue\n",
    "#             ans += val\n",
    "#             v[i] = True\n",
    "#             if i > 0: v[i - 1] = True\n",
    "#             if i < n - 1: v[i + 1] = True\n",
    "#         return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        sort_nums = sorted(range(n), key=lambda x: nums[x])\n",
    "        res = 0\n",
    "        search = [True] * n\n",
    "        for i in sort_nums:\n",
    "            if search[i]:\n",
    "                res += nums[i]\n",
    "                search[i] = False\n",
    "                if i - 1 >= 0:\n",
    "                    search[i-1] = False\n",
    "                if i + 1 < n:\n",
    "                    search[i+1] = False\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n,res=len(nums),0\n",
    "        arr=sorted(range(n),key=lambda x: nums[x])\n",
    "        vis=[False]*n\n",
    "        for i in arr:\n",
    "            if vis[i]:continue\n",
    "            res +=nums[i]\n",
    "            j=1\n",
    "            while i-j>=0 and vis[i-j]:j +=1\n",
    "            if i-j>=0: vis[i-j]=True\n",
    "            j=1\n",
    "            while i+j<n and vis[i+j]:j +=1\n",
    "            if i+j<n: vis[i+j]=True\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n,res=len(nums),0\n",
    "        arr=sorted(range(n),key=lambda x: nums[x])\n",
    "        vis=[False]*(n+2)\n",
    "        for i in arr:\n",
    "            if vis[i]:continue\n",
    "            res +=nums[i]\n",
    "            vis[i-1]=vis[i+1]=True\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n,res=len(nums),0\n",
    "        arr=sorted(range(n),key=lambda x: nums[x])\n",
    "        vis=[False]*(n+2)\n",
    "        for i in arr:\n",
    "            if vis[i]:continue\n",
    "            res +=nums[i]\n",
    "            vis[i-1]=vis[i+1]=True\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        indice = sorted(range(len(nums)), key=lambda k: nums[k])\n",
    "        visit = [0 for i in nums]\n",
    "        score = 0\n",
    "        for i in range(len(indice)):\n",
    "            if not visit[indice[i]]:\n",
    "                score += nums[indice[i]]\n",
    "                visit[indice[i]] = 1\n",
    "                if indice[i] - 1 >= 0:\n",
    "                    visit[indice[i] - 1] = 1\n",
    "                if indice[i] + 1 < len(nums):\n",
    "                    visit[indice[i] + 1] = 1\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# dp\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1: return nums[0]\n",
    "        v = [False] * n\n",
    "        v[0] = True\n",
    "        dps = [0] * n\n",
    "        dps[0] = -nums[0]\n",
    "        ans = nums[0]\n",
    "        idx = 1\n",
    "        for idx in range(1,n):\n",
    "            if dps[idx - 1] != 0 and nums[idx - 1] <= nums[idx]: continue\n",
    "            if dps[idx - 1] != 0 and nums[idx - 1] > nums[idx]:\n",
    "                ans += nums[idx] + dps[idx - 1]\n",
    "                # dps[idx] = nums[idx] - nums[idx - 1] +\n",
    "                dps[idx] = - nums[idx] - dps[idx - 1]\n",
    "            elif dps[idx - 1] == 0:\n",
    "                ans += nums[idx]\n",
    "                dps[idx] = -nums[idx]\n",
    "            print(idx,nums[idx],ans)\n",
    "        print(dps)\n",
    "        return ans\n",
    "\n",
    "\"\"\" \n",
    "[10, 44, 10, 8, 48, 30, 17, 38, 41, 27, 16, 33, 45, 45, 34, 30, 22, 3, 42, 42]\n",
    "[10, 0, 10, -2, 0, 30, -13, 0, 41, -14, -11, 0, 45, 0, 34, -4, -8, -19, 0, 42]\n",
    "2 10 20\n",
    "3 8 18\n",
    "5 30 48\n",
    "6 17 35\n",
    "8 41 76\n",
    "9 27 62\n",
    "10 16 92\n",
    "12 45 137\n",
    "14 34 171\n",
    "15 30 167\n",
    "16 22 193\n",
    "17 3 204\n",
    "19 42 246\n",
    " \"\"\"\n",
    "\n",
    "# 直接模拟\n",
    "# class Solution:\n",
    "#     def findScore(self, nums: List[int]) -> int:\n",
    "#         n = len(nums)\n",
    "#         v = [False] * n\n",
    "#         li = sorted((val,i) for i,val in enumerate(nums))\n",
    "#         ans = 0\n",
    "#         for val,i in li:\n",
    "#             if v[i]: continue\n",
    "#             ans += val\n",
    "#             v[i] = True\n",
    "#             if i > 0: v[i - 1] = True\n",
    "#             if i < n - 1: v[i + 1] = True\n",
    "#         return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        arr = [(x, i) for i,x in enumerate(nums)]\n",
    "        arr.sort()\n",
    "\n",
    "        n = len(nums)\n",
    "        used = [False]*n\n",
    "\n",
    "        ans = 0\n",
    "        for (x, i) in arr:\n",
    "            if not used[i]:\n",
    "                ans += x\n",
    "                if i-1>=0:\n",
    "                    used[i-1] = True\n",
    "                if i+1<n:\n",
    "                    used[i+1] = True\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        lst = list(zip(nums, range(n)))\n",
    "        lst.sort()\n",
    "        vst = [0] * n\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            k, idx = lst[i]\n",
    "            if vst[idx] == 0:\n",
    "                ret += k\n",
    "                if idx > 0:\n",
    "                    vst[idx - 1] = 1\n",
    "                if idx != n - 1:\n",
    "                    vst[idx + 1] = 1\n",
    "                vst[idx] = 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        arr = sorted([(x, i) for i, x in enumerate(nums)])\n",
    "        n = len(nums) \n",
    "        vis = [0] * n \n",
    "        ans = 0 \n",
    "        for j in range(n):\n",
    "            x, i = arr[j] \n",
    "            if vis[i]:\n",
    "                continue \n",
    "            vis[i]=1\n",
    "            if i+1 < n:\n",
    "                vis[i+1] = 1\n",
    "            if i-1 >= 0:\n",
    "                vis[i-1] = 1\n",
    "            ans += x \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        def cmp(a,b):\n",
    "            if nums[a]<nums[b]:\n",
    "                return 1\n",
    "            elif nums[a]>nums[b]:\n",
    "                return -1\n",
    "            elif a>b:\n",
    "                return -1\n",
    "            else:\n",
    "                return 1\n",
    "        score,n = 0, len(nums)\n",
    "        idxs = sorted(list(range(n)), key=functools.cmp_to_key(cmp))\n",
    "        tag = [False]*n\n",
    "        while idxs:\n",
    "            while idxs and tag[idxs[-1]]:\n",
    "                idxs.pop()\n",
    "            if not idxs:\n",
    "                break\n",
    "            tag[idxs[-1]] = True\n",
    "            if idxs[-1]-1>=0:\n",
    "                tag[idxs[-1]-1] = True\n",
    "            if idxs[-1]+1 < n:\n",
    "                tag[idxs[-1]+1] = True\n",
    "            score += nums[idxs[-1]]\n",
    "            idxs.pop()\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ls=[]\n",
    "        mark=[False]*n\n",
    "        for i,j in enumerate(nums):\n",
    "            ls.append((j,i))\n",
    "        ls.sort()\n",
    "        k=0\n",
    "        ret=0\n",
    "        while k<n:\n",
    "            j,i=ls[k]\n",
    "            if mark[i]==True:\n",
    "                k+=1\n",
    "                continue\n",
    "            ret+=j\n",
    "            mark[i]=True\n",
    "            if i>0:\n",
    "                mark[i-1]=True\n",
    "            if i!=n-1:\n",
    "                mark[i+1]=True\n",
    "            k+=1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        a = [i for i in range(n)]\n",
    "        a.sort(key=lambda i: (nums[i], i))\n",
    "        res = 0\n",
    "        for i in a:\n",
    "            if nums[i] > 0:\n",
    "                res += nums[i]\n",
    "                nums[i] = 0\n",
    "                if i > 0:\n",
    "                    nums[i-1] = 0\n",
    "                if i + 1 < n:\n",
    "                    nums[i+1] = 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/u/l00/\n",
    "\n",
    "# 直接模拟\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        v = [False] * n\n",
    "        li = sorted((val,i) for i,val in enumerate(nums))\n",
    "        ans = 0\n",
    "        for val,i in li:\n",
    "            if v[i]: continue\n",
    "            ans += val\n",
    "            v[i] = True\n",
    "            if i > 0: v[i - 1] = True\n",
    "            if i < n - 1: v[i + 1] = True\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = sorted((nums[i], i) for i in range(n))\n",
    "        nums.append(False)\n",
    "        ans = 0\n",
    "        for n, i in s:\n",
    "            if nums[i]:\n",
    "                ans += n\n",
    "                nums[i] = nums[i+1] = nums[i-1] = False\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        heapnums = [(nums[i],i) for i in range(len(nums))]\n",
    "        heapify(heapnums)\n",
    "        ans = 0\n",
    "        while heapnums:\n",
    "            a,i = heappop(heapnums)\n",
    "            if nums[i] == -1:\n",
    "                continue\n",
    "            ans += a\n",
    "            nums[i] = -1\n",
    "            if i-1 >= 0:\n",
    "                nums[i-1] = -1\n",
    "            if i+1 < len(nums):\n",
    "                nums[i+1] = -1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findScore(self, nums: List[int]) -> int:\r\n",
    "        sorted_nums = sorted(enumerate(nums), key=lambda x: x[1])\r\n",
    "        visited = [False] * (len(nums) + 2)\r\n",
    "        ans = 0\r\n",
    "        for i, num in sorted_nums:\r\n",
    "            if not visited[i]:\r\n",
    "                visited[i-1] = visited[i+1] = True\r\n",
    "                ans += num  \r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        judge = [False] * len(nums)\n",
    "        res = 0\n",
    "        p_q = []\n",
    "        heapify(p_q)\n",
    "        for i in range(len(nums)):\n",
    "            temp = (nums[i], i)\n",
    "            heappush(p_q, temp)\n",
    "        while len(p_q) != 0:\n",
    "            temp = heappop(p_q)\n",
    "            if judge[temp[1]] is False:\n",
    "                res += temp[0]\n",
    "                judge[temp[1]] = True\n",
    "                if temp[1] + 1 < len(nums):\n",
    "                    judge[temp[1] + 1] = True\n",
    "                if temp[1] - 1 >= 0:\n",
    "                    judge[temp[1] - 1] = True\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        judge = [False] * len(nums)\n",
    "        res = 0\n",
    "        p_q = []\n",
    "        heapify(p_q)\n",
    "        for i in range(len(nums)):\n",
    "            temp = (nums[i], i)\n",
    "            heappush(p_q, temp)\n",
    "        while len(p_q) != 0:\n",
    "            temp = heappop(p_q)\n",
    "            if judge[temp[1]] is False:\n",
    "                res += temp[0]\n",
    "                judge[temp[1]] = True\n",
    "                if temp[1] + 1 < len(nums):\n",
    "                    judge[temp[1] + 1] = True\n",
    "                if temp[1] - 1 >= 0:\n",
    "                    judge[temp[1] - 1] = True\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        arr = sorted([(x, i) for i, x in enumerate(nums)])\n",
    "        Q = deque(arr) \n",
    "        n = len(nums) \n",
    "        vis = [0] * n \n",
    "        ans = 0 \n",
    "        while Q:\n",
    "            x, i = Q.popleft() \n",
    "            if vis[i]:\n",
    "                continue \n",
    "            vis[i]=1\n",
    "            if i+1 < n:\n",
    "                vis[i+1] = 1\n",
    "            if i-1 >= 0:\n",
    "                vis[i-1] = 1\n",
    "            ans += x \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(enumerate(nums), key=lambda x:x[1])\n",
    "        vis = [False] * (n + 2)\n",
    "        ans = 0\n",
    "        for i, x in nums:\n",
    "            if not vis[i+1]:\n",
    "                vis[i] = vis[i+2] = True\n",
    "                ans += x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        marked = [False] * n\n",
    "        score = 0\n",
    "        \n",
    "        # 初始化优先队列，其中每个元素是 (值, 索引)\n",
    "        heap = [(nums[i], i) for i in range(n)]\n",
    "        heapq.heapify(heap)\n",
    "        \n",
    "        while heap:  \n",
    "            val, idx = heapq.heappop(heap)  # 获取最小值及其索引\n",
    "            # 如果已被标记，直接跳过\n",
    "            if marked[idx]:\n",
    "                continue\n",
    "            score += val  # 更新得分\n",
    "            # 标记该元素及其相邻元素\n",
    "            for j in range(idx - 1, idx + 2):\n",
    "                if 0 <= j < n:\n",
    "                    marked[j] = True\n",
    "                    \n",
    "        return score\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        sorted_num = sorted(enumerate(nums), key=lambda x: x[1])\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        flag = n\n",
    "        vis = [False] * n\n",
    "        i = 0\n",
    "        while flag > 0:\n",
    "            pos = sorted_num[i][0]\n",
    "            if vis[pos] is False:\n",
    "                vis[pos] = True\n",
    "                flag -= 1\n",
    "                ans += nums[pos]\n",
    "                if pos + 1 != n and vis[pos + 1] is False:\n",
    "                    flag -= 1\n",
    "                    vis[pos + 1] = True\n",
    "                if pos - 1 != -1 and vis[pos - 1] is False:\n",
    "                    flag -= 1\n",
    "                    vis[pos - 1] = True \n",
    "            i += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n,res=len(nums),0\n",
    "        arr=sorted(enumerate(nums),key=lambda p:p[1])\n",
    "        vis=[False]*(n+2)\n",
    "        for i,x in arr:\n",
    "            if vis[i]:continue\n",
    "            res +=x\n",
    "            vis[i-1]=vis[i+1]=True\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        visit = [0]*n\n",
    "        stack = [[nums[i], i] for i in range(n)]\n",
    "        stack.sort()\n",
    "        ans = 0\n",
    "        for val, i in stack:\n",
    "            if visit[i]:\n",
    "                continue\n",
    "            ans += val\n",
    "            if i:\n",
    "                visit[i-1] = 1\n",
    "            if i+1<n:\n",
    "                visit[i+1] =1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        length = len(nums)\n",
    "        travelled = [False] * length\n",
    "        for idx, val in sorted(enumerate(nums), key=lambda obj : obj[1]):\n",
    "            if travelled[idx] is True:\n",
    "                continue\n",
    "            # print(idx, val)\n",
    "            else: \n",
    "                # print(val, idx)\n",
    "                ans += val\n",
    "                if idx - 1 >= 0:\n",
    "                    travelled[idx-1] = True\n",
    "                if idx + 1 < length:\n",
    "                    travelled[idx+1] = True\n",
    "                travelled[idx] = True\n",
    "                # print(idx)\n",
    "                # print(travelled)\n",
    "\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        vis = [False] * len(nums)\n",
    "        for i, x in sorted(enumerate(nums), key=lambda p: p[1]):\n",
    "            if not vis[i]:\n",
    "                if i > 0:\n",
    "                    vis[i - 1] = True\n",
    "                if i < len(nums) - 1:\n",
    "                    vis[i + 1] = True\n",
    "                ans += x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        q = queue.PriorityQueue()\n",
    "        for i in range(len(nums)):\n",
    "            q.put([nums[i],i])\n",
    "        vis = [0 for i in range(len(nums))]\n",
    "        res = 0\n",
    "        while not q.empty():\n",
    "            t = q.get()\n",
    "            val,index = t[0],t[1]\n",
    "            if vis[index] == 0:\n",
    "                res += val\n",
    "                vis[index] = 1\n",
    "                if index-1>=0:\n",
    "                    vis[index-1] = 1\n",
    "                if index+1<len(nums):\n",
    "                    vis[index+1] = 1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        from heapq import heapify,heappop,heappush\n",
    "        score=0\n",
    "        pq=[(x,i) for i,x in enumerate(nums)]\n",
    "        heapify(pq)\n",
    "        n=len(nums)\n",
    "        flags=[False]*n\n",
    "        while pq:\n",
    "            x,i=heappop(pq) \n",
    "            if not flags[i]:\n",
    "                score+=x \n",
    "                if i<n-1:\n",
    "                    flags[i+1]=True \n",
    "                if i>0:\n",
    "                    flags[i-1]=True \n",
    "        return score\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        length = len(nums)\n",
    "        travelled = [False] * length\n",
    "        for idx, val in sorted(enumerate(nums), key=lambda obj : obj[1]):\n",
    "            if travelled[idx] is True:\n",
    "                continue\n",
    "            # print(idx, val)\n",
    "            if travelled[idx] is False:\n",
    "                # print(val, idx)\n",
    "                ans += val\n",
    "            if idx - 1 >= 0:\n",
    "                travelled[idx-1] = True\n",
    "            if idx + 1 < length:\n",
    "                travelled[idx+1] = True\n",
    "            travelled[idx] = True\n",
    "            # print(idx)\n",
    "            # print(travelled)\n",
    "\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        arr = [(x, i) for i, x in enumerate(nums)]\n",
    "        heapq.heapify(arr) \n",
    "        n = len(nums) \n",
    "        vis = [0] * n \n",
    "        ans = 0 \n",
    "        while arr:\n",
    "            x, i = heapq.heappop(arr)\n",
    "            if vis[i]:\n",
    "                continue \n",
    "            vis[i]=1\n",
    "            if i+1 < n:\n",
    "                vis[i+1] = 1\n",
    "            if i-1 >= 0:\n",
    "                vis[i-1] = 1\n",
    "            ans += x \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        arr = []\n",
    "        vis = [False] * len(nums)\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "            arr.append((x, i))\n",
    "        arr.sort(key=lambda x: x[0])\n",
    "\n",
    "        for (val, idx) in arr:\n",
    "            if not vis[idx]:\n",
    "                ans += val\n",
    "                if idx - 1 >= 0: \n",
    "                    vis[idx - 1] = True\n",
    "                if idx + 1 < len(nums):\n",
    "                    vis[idx + 1] = True\n",
    "                vis[idx] = True\n",
    "\n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        vis = [False] * (len(nums) + 2)  # 保证下标不越界\n",
    "        for i, x in sorted(enumerate(nums, 1), key=lambda p: p[1]):\n",
    "            if not vis[i]:\n",
    "                vis[i - 1] = vis[i + 1] = True  # 标记相邻的两个元素\n",
    "                ans += x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        vis = [False] * (len(nums) + 2)  # 保证下标不越界\n",
    "        for i, x in sorted(enumerate(nums, 1), key=lambda p: p[1]):\n",
    "            if not vis[i]:\n",
    "                vis[i - 1] = vis[i + 1] = True  # 标记相邻的两个元素\n",
    "                ans += x\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        used = [False] * (n + 2)\n",
    "        for i, x in sorted(enumerate(nums, 1), key=lambda p : p[1]):\n",
    "            if not used[i]:\n",
    "                used[i-1] = used[i+1] = True\n",
    "                ans += x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        vis = [False] * (len(nums) + 2)  # 保证下标不越界\n",
    "        for i, x in sorted(enumerate(nums, 1), key=lambda p: p[1]):\n",
    "            if not vis[i]:\n",
    "                vis[i - 1] = vis[i + 1] = True  # 标记相邻的两个元素\n",
    "                ans += x\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        s=set()   \n",
    "        ans=0\n",
    "        for i,x in sorted(enumerate(nums),key=lambda z:(z[1],z[0])):\n",
    "            if i not in s:\n",
    "                s.add(i)\n",
    "                s.add(i-1)\n",
    "                s.add(i+1)\n",
    "                ans+=x\n",
    "        return ans\n",
    "        '''\n",
    "        #也可以用数组的方式来模拟哈希表\n",
    "        ans=0\n",
    "        vis=[False]*(len(nums)+2)\n",
    "        for i,x in sorted(enumerate(nums,1),key=lambda z:z[1]):\n",
    "            if not vis[i]:\n",
    "                ans+=x\n",
    "                vis[i+1]=vis[i-1]=True  #这是因为把相邻的标记上了，自己肯定不会被再次选中了，本来也就只用标记相邻的\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        h = [(x, i) for i, x in enumerate(nums)]\n",
    "        heapify(h)\n",
    "        vis = [False] * n \n",
    "        ans = 0\n",
    "        while h:\n",
    "            if not vis[h[0][1]]:\n",
    "                x, i = heappop(h)\n",
    "                # print(x, i)\n",
    "                ans += x\n",
    "                for j in range(max(0, i-1), min(i + 2, n)):\n",
    "                    vis[j] = True\n",
    "            else:\n",
    "                heappop(h)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 最小堆\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        hq=[]\n",
    "        flags=[0]*n\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            heapq.heappush(hq,[nums[i],i])\n",
    "        while len(hq):\n",
    "            num,index=heapq.heappop(hq)\n",
    "            if flags[index]==0:\n",
    "                ans+=num\n",
    "                if index-1>=0:flags[index-1]=1\n",
    "                if index+1<n:flags[index+1]=1\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution2:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        # 1 0 5 2 3 4\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        flags=[0]*n\n",
    "        arr=sorted([(num,i) for i,num in enumerate(nums)],key=lambda x:x[0])\n",
    "        for num,index in arr:\n",
    "            if flags[index]==0:\n",
    "                ans+=num\n",
    "                if index-1>=0:flags[index-1]=1\n",
    "                if index+1<n:flags[index+1]=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        jie = 0 \n",
    "        x = [False]*(len(nums)+2)\n",
    "        for i,j in sorted(enumerate(nums,1),key = lambda x:x[1]):\n",
    "            if not x[i]:\n",
    "                x[i]=x[i-1]=x[i+1]= True\n",
    "                jie+=j\n",
    "        return jie "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        vis=[False]*(len(nums)+1)\n",
    "        for i,x in sorted(enumerate(nums,0),key=lambda p:p[1]):\n",
    "            print(i,x)\n",
    "            if not vis[i]:\n",
    "                vis[i-1]=vis[i+1]=vis[i]=True\n",
    "                ans+=x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        hq=[]\n",
    "        flags=[0]*n\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            heapq.heappush(hq,[nums[i],i])\n",
    "        while len(hq):\n",
    "            num,index=heapq.heappop(hq)\n",
    "            if flags[index]==0:\n",
    "                ans+=num\n",
    "                if index-1>=0:flags[index-1]=1\n",
    "                if index+1<n:flags[index+1]=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        length = len(nums)\n",
    "        travelled = [False] * length\n",
    "        for idx, val in sorted(enumerate(nums), key=lambda obj : obj[1]):\n",
    "            if travelled[idx] is True:\n",
    "                continue\n",
    "            ans += val\n",
    "            if idx - 1 >= 0:\n",
    "                travelled[idx-1] = True\n",
    "            if idx + 1 < length:\n",
    "                travelled[idx+1] = True\n",
    "            travelled[idx] = True\n",
    "\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        k=[False]*n\n",
    "        ans=0\n",
    "        b=[i for i in range(n)]\n",
    "        def sort_a_by_b(a, b):\n",
    "            return [x for _, x in sorted(zip(b, a))]\n",
    "        b=sort_a_by_b(b,nums)\n",
    "        for i in b:\n",
    "            if k[i]:\n",
    "                continue\n",
    "            ans+=nums[i]\n",
    "            if i>0:\n",
    "                k[i-1]=True\n",
    "            if i<n-1:\n",
    "                k[i+1]=True\n",
    "            k[i]=True\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        sorted_idx = sorted(list(range(n)), key=lambda i: (nums[i], i))\n",
    "        score = 0\n",
    "        for i in sorted_idx:\n",
    "            if nums[i]:\n",
    "                score += nums[i]\n",
    "                if i > 0:\n",
    "                    nums[i-1] = 0\n",
    "                if i < n-1:\n",
    "                    nums[i+1] = 0\n",
    "        \n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        vis = [0] * (n + 2) \n",
    "        arr = [(x, i+1) for i, x in enumerate(nums)]\n",
    "        heapq.heapify(arr) \n",
    "        ans = 0\n",
    "        while arr:\n",
    "            x, idx = heapq.heappop(arr) \n",
    "            if vis[idx]:\n",
    "                continue \n",
    "            vis[idx] = vis[idx-1] = vis[idx+1] = 1 \n",
    "            ans += x \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        marked = [False for _ in range(n)]\n",
    "        l = sorted(enumerate(nums), key=lambda x:x[1])\n",
    "        for i, num in l:\n",
    "            if marked[i]: continue\n",
    "            res += num\n",
    "            marked[i] = True\n",
    "            if i > 0: marked[i-1] = True\n",
    "            if i < n-1: marked[i+1] = True\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 最小堆\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        hq=[]\n",
    "        flags=[0]*n\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            heapq.heappush(hq,[nums[i],i])\n",
    "        while len(hq):\n",
    "            num,index=heapq.heappop(hq)\n",
    "            if flags[index]==0:\n",
    "                ans+=num\n",
    "                if index-1>=0:flags[index-1]=1\n",
    "                if index+1<n:flags[index+1]=1\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        # 1 0 5 2 3 4\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        flags=[0]*n\n",
    "        arr=sorted([(num,i) for i,num in enumerate(nums)],key=lambda x:x[0])\n",
    "        for num,index in arr:\n",
    "            if flags[index]==0:\n",
    "                ans+=num\n",
    "                if index-1>=0:flags[index-1]=1\n",
    "                if index+1<n:flags[index+1]=1\n",
    "        return ans                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        vis=[0]*n\n",
    "        ans=0\n",
    "        print(sorted(zip(nums,range(n))))\n",
    "        for v,idx in sorted(zip(nums,range(n))):\n",
    "            if vis[idx]==1:\n",
    "                continue\n",
    "            vis[idx]=1\n",
    "            ans+=v\n",
    "            for nex in [idx+1,idx-1]:\n",
    "                if 0<=nex<n:\n",
    "                    vis[nex]=1\n",
    "        #print(vis)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        mark = [False] * n\n",
    "        def cmp(a, b) :\n",
    "            if a[0] == b[0]:\n",
    "                return a[1] - b[1]\n",
    "            else:\n",
    "                return a[0] - b[0]\n",
    "\n",
    "        sortedIndex = list(zip(nums, [i for i in range(n)]))\n",
    "        sortedIndex.sort(key=cmp_to_key(cmp))\n",
    "        print(sortedIndex)\n",
    "        ans = 0\n",
    "        for sortIdx in sortedIndex:\n",
    "            if not mark[sortIdx[1]]:\n",
    "                ans += sortIdx[0]\n",
    "\n",
    "                if sortIdx[1] - 1 >= 0:\n",
    "                    mark[sortIdx[1] - 1] = True\n",
    "                if sortIdx[1] + 1 < n:\n",
    "                    mark[sortIdx[1] + 1] = True\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        sl = SortedList()\n",
    "        for i, nu in enumerate(nums):\n",
    "            sl.add((nu, i))\n",
    "        res = 0\n",
    "        seen = set()\n",
    "        while sl:\n",
    "            nu, i = sl[0]\n",
    "            # print(nu, i)\n",
    "            sl.remove(sl[0])\n",
    "            seen.add(i)\n",
    "            if i > 0 and i - 1 not in seen:\n",
    "                sl.remove((nums[i - 1], i - 1))\n",
    "                seen.add(i - 1)\n",
    "            if i < n - 1 and i + 1 not in seen:\n",
    "                sl.remove((nums[i + 1], i + 1))\n",
    "                seen.add(i + 1)\n",
    "            seen.add(i)\n",
    "            res += nu\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        q = [(v, i) for i, v in enumerate(nums)]\n",
    "        q.sort(key=lambda x: (x[0], x[1]))\n",
    "        n, ans = len(nums), 0\n",
    "        used = [False] * n\n",
    "        for v, i in q:\n",
    "            if used[i]:\n",
    "                continue\n",
    "            for j in range(max(0, i - 1), min(i + 2, n)):\n",
    "                used[j] = True\n",
    "            ans += v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        heap = []\n",
    "        vis = set()\n",
    "        res = 0\n",
    "        for i, n in enumerate(nums):\n",
    "            heapq.heappush(heap, (n, i))\n",
    "        \n",
    "        while heap:\n",
    "            n, i = heapq.heappop(heap)\n",
    "            if i in vis: continue\n",
    "            \n",
    "            vis.add(i)\n",
    "            vis.add(i + 1)\n",
    "            vis.add(i - 1)\n",
    "            res += n\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        a = sorted([(x, i) for i, x in enumerate(nums)])\n",
    "        mark = set() \n",
    "        ans = 0\n",
    "        for x, i in a:\n",
    "            if i in mark: continue\n",
    "            ans += x\n",
    "            mark.add(i) \n",
    "            if i - 1 >= 0:                \n",
    "                mark.add(i - 1)\n",
    "            if i + 1 <len(nums):                \n",
    "                mark.add(i + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        visited = set()\n",
    "        h = []\n",
    "        for i, num in enumerate(nums):\n",
    "            heapq.heappush(h, (num, i))\n",
    "        \n",
    "        ans = 0\n",
    "        while len(visited) < len(nums):\n",
    "            n, i = heapq.heappop(h)\n",
    "            if i not in visited:\n",
    "                ans += n\n",
    "                visited.add(i)\n",
    "                if i-1 >= 0:\n",
    "                    visited.add(i-1)\n",
    "                if i+1 < len(nums):\n",
    "                    visited.add(i+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        arr = []\n",
    "        vis = [False] * len(nums)\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "            arr.append((x, i))\n",
    "        arr.sort(key=lambda x: (x[0], x[1]))\n",
    "\n",
    "        for (val, idx) in arr:\n",
    "            if not vis[idx]:\n",
    "                ans += val\n",
    "                if idx - 1 >= 0: \n",
    "                    vis[idx - 1] = True\n",
    "                if idx + 1 < len(nums):\n",
    "                    vis[idx + 1] = True\n",
    "                vis[idx] = True\n",
    "\n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        num2idx = sorted((num, idx) for idx, num in enumerate(nums))\n",
    "\n",
    "        res = 0\n",
    "        hashset = set()\n",
    "        hashset |= {-1, n}\n",
    "\n",
    "        for num, idx in num2idx:\n",
    "            if idx in hashset:\n",
    "                continue\n",
    "\n",
    "            res += num\n",
    "            hashset.add(idx)\n",
    "\n",
    "            if idx - 1 not in hashset:\n",
    "                hashset.add(idx - 1)\n",
    "\n",
    "            if idx + 1 not in hashset:\n",
    "                hashset.add(idx + 1)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        result, h, v = 0, [(x, i) for i, x in enumerate(nums)], set()\n",
    "        heapify(h)\n",
    "        while h:\n",
    "            x, i = heappop(h)\n",
    "            if not i in v:\n",
    "                result += x\n",
    "                v.update(range(i-1, i+2))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        num2idx = sorted(\n",
    "            (num, idx) for idx, num in enumerate(nums))\n",
    "\n",
    "        res = 0\n",
    "        hashset = set()\n",
    "\n",
    "        for num, idx in num2idx:\n",
    "            if idx in hashset:\n",
    "                continue\n",
    "\n",
    "            res += num\n",
    "            hashset.add(idx)\n",
    "        \n",
    "            if idx - 1 >= 0 and idx - 1 not in hashset:\n",
    "                hashset.add(idx - 1)\n",
    "                \n",
    "            if idx + 1 < n and idx + 1 not in hashset:\n",
    "                hashset.add(idx + 1)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        a = list(zip(nums, range(n))) \n",
    "        a.sort(key = lambda x : (x[0], x[1])) \n",
    "        a = deque(a)\n",
    "        used = [False] * n \n",
    "        ans = 0 \n",
    "        while a : \n",
    "            x, idx = a.popleft() \n",
    "            if used[idx] : continue \n",
    "            ans += x \n",
    "            if idx - 1 >= 0 : used[idx - 1] = True \n",
    "            if idx + 1 < n : used[idx + 1] = True \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        score=0\n",
    "        n=len(nums)\n",
    "        dp=list(zip(nums,range(n)))\n",
    "        dp.sort(key=lambda x:(x[0],x[1]))\n",
    "        key=[True for i in range(n)]\n",
    "        for number,i in dp:\n",
    "            if key[i]:\n",
    "                score+=number\n",
    "                key[i]=False\n",
    "                key[max(0,i-1)]=False\n",
    "                key[min(n-1,i+1)]=False\n",
    "        return score\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "\n",
    "        score = 0\n",
    "        lennum = len(nums)\n",
    "        nums = list(zip(nums, range(lennum)))\n",
    "        heapq.heapify(nums)\n",
    "        marked = set()\n",
    "        while nums:\n",
    "            n, ind = heapq.heappop(nums)\n",
    "            if ind not in marked:\n",
    "                score += n\n",
    "                for ii in [max(0, ind-1), ind, min(ind+1, lennum-1)]:\n",
    "                    marked.add(ii)\n",
    "        \n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        pq = [(n, i)for i, n in enumerate(nums)]\n",
    "        heapq.heapify(pq)\n",
    "        ans = 0\n",
    "        seen = set()\n",
    "        while pq:\n",
    "            val, idx = heapq.heappop(pq)\n",
    "\n",
    "            ans += val\n",
    "\n",
    "            seen.add(idx)\n",
    "\n",
    "            if idx - 1 >= 0:\n",
    "                seen.add(idx - 1)\n",
    "            \n",
    "            if idx + 1 < len(nums):\n",
    "                seen.add(idx + 1)\n",
    "\n",
    "            while pq and pq[0][1] in seen:\n",
    "                heapq.heappop(pq)\n",
    "        \n",
    "\n",
    "\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        flag = [0] * n\n",
    "        ans = 0\n",
    "        for i, x in sorted(enumerate(nums), key=lambda x:[x[1], x[0]]):\n",
    "            if flag[i] == 1: continue\n",
    "            ans += x\n",
    "            flag[i] = 1\n",
    "            if i > 0: flag[i - 1] = 1\n",
    "            if i < n - 1: flag[i + 1] = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = [[num,index+1] for index,num in enumerate(nums)]\n",
    "        nums = sorted(nums,key = lambda x:(x[0],x[1]))\n",
    "        nums.append([10000000,0])\n",
    "        nums.append([10000000,n+1])\n",
    "        numsindex = [-1 for i in range(n+2)]\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if(numsindex[nums[i][1]]==-1):\n",
    "                res += nums[i][0]\n",
    "                numsindex[nums[i][1]]=0\n",
    "                numsindex[nums[i][1]-1]=0\n",
    "                numsindex[nums[i][1]+1]=0\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        nums = list(enumerate(nums))\n",
    "        hashtable = defaultdict(int)\n",
    "        nums.sort(key=lambda x:x[1])\n",
    "        res = 0\n",
    "        for idx, num in nums:\n",
    "            if hashtable[idx]:\n",
    "                continue\n",
    "            res+=num\n",
    "            hashtable[idx]=1\n",
    "            hashtable[idx-1]=1\n",
    "            hashtable[idx+1]=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        import heapq\n",
    "        pq = []\n",
    "        for i in range(len(nums)):\n",
    "            heapq.heappush(pq, (nums[i], i))\n",
    "        \n",
    "        from collections import defaultdict\n",
    "        vis = defaultdict(int)\n",
    "        res = 0\n",
    "        while pq:\n",
    "            number, index = heapq.heappop(pq)\n",
    "            if vis[index] == 0:\n",
    "                vis[index], vis[index-1], vis[index+1] = 1, 1, 1\n",
    "                res += number\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = [[num,index+1] for index,num in enumerate(nums)]\n",
    "        nums = sorted(nums,key = lambda x:(x[0],x[1]))\n",
    "        nums.append([10000000,0])\n",
    "        nums.append([10000000,n+1])\n",
    "        numsindex = [-1 for i in range(n+2)]\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if(numsindex[nums[i][1]]==-1):\n",
    "                res += nums[i][0]\n",
    "                numsindex[nums[i][1]]=0\n",
    "                numsindex[nums[i][1]-1]=0\n",
    "                numsindex[nums[i][1]+1]=0\n",
    "        print(nums)\n",
    "        print(numsindex)\n",
    "        \n",
    "        \n",
    "        \n",
    "        return res        \n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
